Most prior art racing video games use polygon collision detection for modeling the interaction between the race track and the racecar. Today's technology allows very realistic physics to be used to model the cars used in racecar games. For example, the suspension and tire friction of the virtual cars are very sensitive to load changes (i.e., the amount of weight that is on the tire). These realistic cars can provide much more realistic and exciting gameplay for the user. However, when polygons are used to express the road, the surface of the road abruptly changes direction each time a polygon vertex is reached. FIG. 1 illustrates this point and shows a section of a polygon track 200 with vertexes 204 and 206. As can be seen from FIG. 1, the polygon track presents a piecewise linear surface on which the car tire 206 rides. As the car tire passes over vertex 204, the tire 206 will suddenly lose contact with the road 200. This will occur again when the tire 206 passes over vertex 202. The number of polygons can be increased in order to help smooth the road surface. However, the polygon surface still remains piece-wise linear. Moreover, increasing the number of polygons becomes expensive and eventually impractical in terms of CPU time. Thus, most prior art racing games that use polygons for the road surface have relatively abrupt vertices that detrimentally impact the performance of the cars and prevent true tire loading from being used in the model. This impact is further magnified as the sophistication of the car modeling in terms of suspension, tire friction and the like increases. Thus, when sophisticated cars are used on a polygon based track, the polygon-based collision detection becomes a problem in terms of car performance and handling. For example, every time a tire on the car comes off of a polygon (i.e., passes from one polygon to the next) the tire experiences a large load change (like jumping off a ramp). In other words, as soon as the tire goes over a vertex on the piece-wise linear surface defined by the polygons, the load will suddenly and drastically decrease or increase (depending on the nature or direction of the vertex), thereby causing the car to suddenly react in a manner that could cause a spin-out or other type of undesirable control problem that reduces the enjoyment of the game. As a result, most racecar games do not use realistic tire loading and/or use blending techniques to minimize the effect of the load changes. However, these techniques limit the realism of the game. Real cars have tires connected to the body of the car with suspension and a spring or shock absorber that enables the tire to rotate relative to the car within the constraints of the suspension and in response to loading of the tire. FIG. 4 depicts an exemplary car with car body 208 connected to two wheels (210, 212) through suspension 214 and springs 220 Thus, in order to realistically model a car in a game, accurate loading and suspension effects should be used. Otherwise, a turning car will not look realistic, as indicated by the car 208′ of FIG. 5. In order to be realistic, the turning car should look more like FIG. 6 in which the suspension effect and tire loading can be seen. Thus, further improvements in track modeling and collision detection are needed for racecar games and the like.
The instant inventor realized that by specifying the track as a spline (rather than by polygons), the surface will be smooth which prevents the vertex problem described above and enables the tire to maintain contact with the road. FIG. 2 illustrates the infinitely smooth road 222 that results from the use of a spline 224. As indicated by FIG. 3, splines can be used on a patch, such as a patch 228 that has various control points 230 that can be manipulated to define a specific splined surface 232 for the patch. However, using patches and splines in this manner creates a problem in that finding the distance from the tire to the surface for load calculations is very complex. Specifically, in order to make an accurate calculation, the patch 228 must be repeatedly subdivided to locate the tire on the patch and then to determine the distance from the patch. This calculation procedure is very expensive in terms of CPU processing time. Thus, improvements are needed in surface modeling that enables splines to be used for collision detection in an efficient and advantageous manner, and which thereby enable sophisticated car modeling, in terms of tire loading, suspension, friction and/or the like, to be used without the adverse affects resulting from polygon modeling.
The present invention addresses this need by providing an improved method and apparatus for using splines in track modeling. In the preferred embodiment, the system of the invention uses arcs and splines to calculate 200 times a second where, for a given piece of road and car state, how much the tire has penetrated into the road. This information is then used to force the tire back up, which forces the suspension back up and, in turn, forces the body up through the springs (see FIG. 4). This enables very realistic car modeling. For example, the tire no longer has to be displayed as always parallel to the body (i.e., with no camber changes), as seen in FIG. 5. Instead, the instant invention enables sophisticated car modeling to be used that provides for tire camber changes based on suspension load, as indicated in FIG. 6. However, in order to use this sophisticated car modeling, accurate tire loading is needed. The arc and spline-based modeling of the instant invention enables accurate tire loading to be used in an efficient and advantageous manner, thereby enabling much more realistic car modeling (in terms of suspension etc.) to be used.
In accordance with the instant invention, arcs are used to represent the curved sections of a track, and splines (e.g., one-dimensional Hermite Splines) are defined around the arcs to specify the height changes for each arc (e.g., each side of the road), thereby enabling complex roads (or other tracks) to be modeled in a very efficient and smooth manner, as compare to prior art techniques. The invention defines a track by defining straight track sections (defined by length) and arced track sections (defined by distance or radius and angles). As explained in greater detail below, splines are defined through the arcs for use in defining the track surface and edges. The length and angles of the arced sections can vary such that any desired type of curved section can be defined for the track. In this way, the track can be defined as a series of straight sections and a series of different arced sections. In accordance with the invention, the track (straights and arcs) are first defined in top-down, plan 2D manner and then the height of the track is applied later. As a result, one can use aerial maps of real racetracks and then lay out the series of straights and arcs in a manner that corresponds to the real track. All real-world tracks have turns defined by the number of degrees and the meter radius of the corner. Thus, the invention is very applicable to real-world modeling of tracks. In addition to the track itself, medians, grass areas, banks and/or other inner or outer arced sections can be defined for each arced road section. Each section can then be defined with a different texture.
Once the 2-D arcs are defined, the splines are then defined to add height to each road section. The spline data can also be used to, for example, add objects to the track, like a fence. In other words, the spline data can be used to generate graphics for the track. As a result, the invention provides the option of having an artist first lay out the track and then apply the straights and arcs thereon, or, alternatively, having the graphics generated directly from the defined arcs and straights. The inventor has developed a test track using the instant invention wherein sixty random arcs are joined together to define a five mile course. Thus, the invention makes it very easy to create very long and interesting courses with many objects, such as trees, and using far less resources as compared to the polygon method.
In accordance with the invention, the elevation of the arcs are defined by specifying an elevation (e.g., in meters) and a height change for the start and the end points of the arc. Then the spline data is generated using a Hermite Spline interpolation. A spline is a parametric curve defined by some control points. A Hermite Spline is known as a curve (typically cubic) for which the user provides the end points of the curve and the parametric derivatives of the curve at the end points. A point on a Hermite curve can be obtained by multiplying each control point by some function and summing. In other words, in the instant invention, the height and the height change is blended from one end point to the other end point over the curve, thereby defining the Hermite Spline data for the arc.
In accordance with the invention, a bounding box is defined for each arc and straight section of the track. The bounding boxes are used to quickly determine if the wheels are anywhere within the area defined by the bounding box. This simplifies testing for the location of the wheels by doing a rough test first in order to eliminate many bounding boxes (and the corresponding sections of track) as possibilities for the location of the wheels. Once it is determined that a wheel is in a bounding box, a 2D test is run to determine whether the wheel in the bounding box is within the minimum and maximum radius of the arc segment. If not, the wheel is not in the arc segment. On the other hand, if the wheel is within the arc segment, a calculation is done to determine how far the wheel is around the arc (arc angle U), in order to determine how the spline is interpolating at that point. Thus, a normalized distance value (0 to 1 value) from the center of the arc is obtained. With this value, the height and elevation change of the arc at the determined points can be determined, thereby providing the data for the Hermite Spline. Next, a temporary plane is found for arc angle U, which is the plane in which the collision may occur. The temporary plane is defined by the normal perpendicular to the road at angle U and the distance from the origin. Then, a calculation is performed to find the distance between the wheel (modeled as a sphere) and that plane. An advantage of the invention is that the above process only needs to be done once per arc segment which is much more efficient than a polygon technique. Once the distance is obtained, it is known how far the tire has embedded itself into the road, thereby enabling a corresponding force to be applied to the tire. This process simulates the compression of the tire under weight. Also, because the angle of the temporary plane is known, the camber angle of the tire can also be determined for simulation purposes (e.g., adjusting frictional values). The force can be changed to simulate air pressure. Once the force is applied to the tire, the car modeling causes resulting forces to the car through the suspension and body modeling, thereby providing a very realistic auto racing game or the like.